package demo25;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[]args){
        int []array={3,1,6,3,4,8,0,9,5};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(array));
        insert(array);
        System.out.println("插入法排序后：");
        System.out.println(Arrays.toString(array));
    }
    //插入法排序
    public static void insert(int[]array){
        for(int i=array.length-1;i>=0;i--){
            int t=array[i];
            int j=i-1;
            for(;j>=0;j--){
                if(array[j]>t){
                    array[j+1]=array[j];
                }else{
                    array[j+1]=t;
                    break;
                }
            }
            array[j+1]=t;

        }
    }
    //希尔排序
    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap/=2;//分组范围由大到小
            shell(array,gap);
        }
    }
    public static void shell(int[] array, int gap){
        for(int i=gap;i<array.length;i++){
            int temp=array[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(array[j]>temp){
                    array[j+gap]=array[j]; // 找到比i索引大的将i前一个gap距离把大于它的这个元素移动到j+gap（i处）处
                }else{
                    array[j+gap]=temp;//没找到保持原位置值
                    break;
                }
            }
            array[j+gap]=temp;//1.若上一个for没找到维持原值2.上面for已经组头与组尾中头把尾覆盖，temp是头尾最小元素，把它放到组头去到最后一组时后面全是比他大的，把最小的放在前面
        }
    }
}
